#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;

/*HJJ QQ479287006
 *输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
static ListNode *reversNode2(ListNode *node) {
    if (node == nullptr || node->next == nullptr)
        return node;


    // 1 2 3 4
    ListNode *p = reversNode2(node->next);//递归到最后一个 这个必须写在前面。。感觉有点不一样

    //其实这边算是单个的头 一个一个翻转的 这里p返回的感觉不像一个整体
    node->next->next = node;//翻转 挺精华的
    node->next = nullptr;//


    return p;

}


ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {

    if (!l1)
        return l2;
    if (!l2)
        return l1;

    // 1 2
    //  2->head
    ListNode *head = nullptr;//这里得使用尾插法。。我这里头差然后旋转的 ///也可以申请一个空间然后返回next就行 了

    while (l1 && l2) {
        ListNode *tempNext;
        if (l1->val < l2->val) {
            tempNext = l1->next;
            l1->next = head;
            head = l1;
            l1 = tempNext;
        } else {
            tempNext = l2->next;
            l2->next = head;
            head = l2;
            l2 = tempNext;
        }

    }
    ListNode *tempNext;
    while (l1) {
        tempNext = l1->next;
        l1->next = head;
        head = l1;
        l1 = tempNext;
    }
    while (l2) {
        tempNext = l2->next;
        l2->next = head;
        head = l2;
        l2 = tempNext;
    }

    return head;
}

//递归
// 函数返回合并后的首节点
ListNode *mergeTwoListsD(ListNode *l1, ListNode *l2) {

    if (!l1)
        return l2;
    if (!l2)
        return l1;

    //1 1 2 5
    //3 7
    if (l1->val < l2->val) {
        l1->next = mergeTwoListsD(l1->next, l2);
    } else {
        l2->next = mergeTwoListsD(l1, l2->next);
    }

    return l1->val < l2->val ? l1 : l2;
}